#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

void TestHeap1()
{
	int a[] = { 4,2,8,1,5,6,9,7,22,333,44,555,88};
	HP hp;
	HPInit(&hp);
	for (size_t i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	
	/*while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}*/
	int k = 0;
	scanf("%d", &k);
	while (k--)
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}

	printf("\n");

}

//堆排序，O(N*logN)
//冒泡排序 O(N^2)
void HeapSort(int* a, int n)
{
	//降序，建大堆（代价太大，关系全乱了）
	//降序，建小堆
	//升序，建大堆
	for (int i = 1; i < n; i++)
	{
		AdjustUP(a, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;//就变成n-2,下一个就是n-3
	}
}
void TestHeap2()
{
	int a[] = { 4,2,8,1,5,6,9,7 };
	HeapSort(a, sizeof(a) / sizeof(int));
}


#if 0
void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}

	fclose(fin);
}

void PrintTopK()
{
	int k;
	printf("请输入k>:");
	scanf("%d", &k);
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}

	// 读取文件中前k个数
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	// 建K个数的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}

	// 读取剩下的N-K个数
	int x = 0;
	while (fscanf(fout, "%d", &x) > 0)
	{
		if (x > kminheap[0])
		{
			kminheap[0] = x;
			AdjustDown(kminheap, k, 0);
		}
	}

	printf("最大前%d个数：", k);
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}
#endif



typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	//BTNode* node7 = BuyNode(6);

	node1->left = node2;
	node2->left = node3;
	node1->right = node4;
	node4->left = node5;
	node4->right = node6;
	//node5->right = node7;

	return node1;

}

void prevOrder(BTNode*root)
{
	if (root ==NULL)
	{
		printf("N ");
		return;
	}
	//前序遍历：根左右
	printf("%d ", root->data);
	prevOrder(root->left);
	prevOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	//中序遍历：左 根 右
	
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	//后序遍历 左 右 根
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

void BinaryTreeDestory(BTNode** root)
{

}
int BinaryTreeSize(BTNode* root)
{
	return root==NULL ? 0 :
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;

}
//没有孩子的即为叶子节点
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (BinaryTreeLeafSize(root->left) == 0 && BinaryTreeLeafSize(root->right) == 0)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

 
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

}


//int fmax(int x, int y)
//{
//	return x > y ? x : y;
//}
//int TreeHeight(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1;
//}


int TreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (root != NULL && k == 1)
		return 1;
	if (root != NULL && k > 1)
		return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data==x)
		return root;
	BTNode* ret1 = TreeFind(root->left,x);
	if(ret1)
		return ret1;
	BTNode* ret2=TreeFind(root->right,x);
	if(ret2)
		return ret2;

	return NULL;
}

int main()
{
	//CreateNDate();
	//PrintTopK();

	BTNode* root = CreatBinaryTree();
	prevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	printf("TreeSize: %d", BinaryTreeSize(root));
	printf("\n");
	printf("TreeLeafSize: %d\n", BinaryTreeLeafSize(root));
	printf("TreeHight: %d\n", TreeHeight(root));
	printf("TreeLevelKSize: %d\n", TreeLevelKSize(root, 2));
	printf("TreeFind: %d\n",TreeFind(root, 2));

	return 0;
}

